#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef struct BinaryTreeNode
{
	int  data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;




}BTNode;
BTNode* buynewnode(int x)
{  
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");

	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
BTNode* createdata()
{
	BTNode* n1 = buynewnode(1);
	BTNode* n2 = buynewnode(2);
	BTNode* n3 = buynewnode(3);
	BTNode* n4 = buynewnode(4);
	BTNode* n5 = buynewnode(5);
	BTNode* n6 = buynewnode(6);
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
	return n1;

}
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ",root->data);
	PreOrder(root->left);
	PreOrder(root->right);


}
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	
	PostOrder(root->right);
	printf("%d ", root->data);




}
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);




}
//int size = 0;
//void BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//		return;
//
//	size++;
//
//	BinaryTreeSize(root->left);
//	BinaryTreeSize(root->right);
//
//
//}
//int BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//		return 0;
//	return  BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
//
//
//
//
//
//}
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;




}

int  BinaryTreeLeafSize(BTNode* root)
{

	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}


	return  BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);



}
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
		return 0;
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);











}
//int BTreeHeight(BTNode* root)
//{
//	if (root == NULL)
//		return 0;
//	return BTreeHeight(root->left) > BTreeHeight(root->right) ? BTreeHeight(root->left) + 1 : BTreeHeight(root->right) + 1;
//
//
//
//
//
//
//}

int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int left = BTreeHeight(root->left)+1;
	int right = BTreeHeight(root->right)+1;
	return left > right ? left : right;





}






int main()
{
	BTNode* st = createdata();
	PreOrder(st);
	printf("\n");
	PostOrder(st);
	printf("\n");
	InOrder(st);
	printf("\n");
	/*BinaryTreeSize(st);
	printf("%d", size);*/
	printf("%d ", BinaryTreeSize(st));
	printf("\n");
	printf("%d ", BinaryTreeLeafSize(st));
	printf("\n");
	printf("%d ", BinaryTreeLevelKSize(st, 1));
	printf("\n");
	printf("%d ", BTreeHeight(st));

}